class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        fa = new int[edges.length+1];
        int[] ans = new int[2];
        for(int i=0; i<=edges.length; i++)fa[i]=i;
        for(int i=0; i<edges.length; i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(find(a)==find(b)){
                ans=edges[i];
                break;
            }else{
                unionSet(a, b);
            }
        }
        return ans;
    }
    private int[] fa;
    private int find(int x){
        if(x==fa[x])return x;
        return fa[x] = find(fa[x]);
    }
    private void unionSet(int x, int y){
        x = find(x);
        y = find(y);
        if(x!=y) fa[x]=y;        
    }
}